#include<bits/stdc++.h>
using namespace std;

const int N = 510; // edge number;

int g[N][N]; // 邻接表
int dist[N]; // 源点到各个点的 最小值
bool st[N]; // 标记是否找到最短路径

// 遍历所有的点
int Dijkstra() {
    // 初始化所有点的距离为正无穷,起始点的距离为0
    memset(dist, 0x3f, sizeof dist);
    
    dist[1] = 0;
    
    for (int i = 0; i < n; i ++ ) {
        int t = -1; // 不在s中的，距离最近的点
        for (int j = 1; j <= n; j++) 
            // !st[j]表示当前点还没确定最短路
            // 在st[j] == false的点中 找到一个 dist距离最短的点（源点）进行延伸
            if (!st[j] && (t == -1 || dist[t] > dist[j])) 
                t = j;
        // 把st这个点标志为已经是 起点1 到 某一个点的最短距离
        st[t] = true; 
        
        // 更新 这个源点到其他点的最短值
        for (int j = 1; j <= n; j++)
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }
    
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    scanf("%d%d", &n, &m);
    // 邻接矩阵的初始化
    memset(g, 0x3f, sizeof g);
    
    while (m -- ) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        // 去掉自环 和 多源路线的最小值
        g[a][b] = min(g[a][b], c);
    }

    int t = Dijkstra();
    
    printf("%d", t);
    
    return 0;
}